package Algorithms.chapter2_1;
import Algorithms.Stopwatch;

public class Example {

    private static boolean less(Comparable v,Comparable w){
        //v<w true
        return v.compareTo(w)<0;
    }
    private static void exch(Comparable[] a,int i,int j){
        Comparable t=a[i];a[i]=a[j];a[j]=t;
    }
    private static void show(Comparable[] a){ //堆排序修改
        for(int i=1;i<a.length;i++){
            System.out.print(a[i]+" ");
        }
        System.out.println();
    }
    public static boolean isSorted(Comparable[] a){//堆排序修改
        for (int i =2;i<a.length;i++){
            if(less(a[i],a[i-1])) return false;
        }
        return true;
    }
    public static String[] radom(int m){//堆排序修改
        //生成随机字母
        String chars = "abcdefghijklmnopqrstuvwxyz";
        String[] re = new String[m+1];
        for(int i=1;i<=m;i++){
            re[i] = String.valueOf(chars.charAt((int)(Math.random() * 26)));
        }
        return re;
    }
    public static void Selection_sort(Comparable[] a){
        int N=a.length;
        for(int i=0;i<N;i++){
            int min = i;
            for(int j=i+1;j<N;j++){
                if(less(a[j],a[min])) min=j;
            }
            exch(a,i,min);
        }
    }
    public static double timeTtial(String[] a){
        Stopwatch timer=new Stopwatch();
        //Selection_sort(a); //选择
        //Insertion_sort(a);   //插入
        //Shell_sort(a); //希尔
        //sort_merge_hilo(a);//并归

        //sort_quick(a);//快速排序
        sort_heap(a);//堆排序
        double result = timer.elapsedTime();
        return result;
    }
    public static void experiment(){
        System.out.println("倍率实验：");
        double prev = timeTtial(radom(125));
        for(int N =250;true;N+=N) {
            double time = timeTtial(radom(N));
            System.out.printf("%6d %7.1f", N, time);
            System.out.printf("%5.1f\n", time / prev);
            prev = time;
        }
    }
    public static void Insertion_sort(Comparable[] a){
        int N=a.length;
        for(int i = 1;i<N;i++){
            for(int j = i;j>0&&less(a[j],a[j-1]);j--){
                exch( a , j ,j-1);
            }
        }
    }
    public static void Shell_sort_error(Comparable[] a){
        int N=a.length;
        int h=1;
        while(h<N){
            h = h*3+1;
        }
        for(;h>=1;h=h/3){
            for(int i=h;i<N;i++){
                for(int j = i;j>=h;j=j-h){
                    if(less(a[j],a[j-h])) exch(a,j,j-h);
                }
            }
        }
    }
    public static void Shell_sort(Comparable[] a){
        int N=a.length;
        int h=1;
        while(h<N){
            h = h*3+1;
        }
        for(;h>=1;h=h/3){
            for(int i=h;i<N;i++){
                for(int j = i;j>=h&&less(a[j],a[j-h]);j=j-h){
                    exch(a,j,j-h);
                }
            }
        }
    }
    private static Comparable[] aux; //私人变量，辅助aux
    public static void sort_merge_hilo(Comparable[]a){
        aux = new Comparable[a.length];
        sort_merge_hilo(a,0,a.length-1);
    }
    private static void sort_merge_hilo(Comparable[]a,int lo,int hi){
        if(lo>=hi) return;
        int mid=lo+(hi-lo)/2;
        sort_merge_hilo(a,lo,mid);
        sort_merge_hilo(a,mid+1,hi);
        merge(a,lo,mid,hi);
    }
    public static void sort_merge_BU(Comparable[]a){
        int N=a.length;
        aux = new Comparable[N];
        for(int sz=1;sz<N;sz=sz+sz){
            for(int lo=0;lo<N-sz;lo=lo+sz+sz){
                merge(a,lo,lo+sz-1,Math.min(lo+sz+sz-1,N-1));
            }
        }
    }
    public static void sort_quick(Comparable[] a){
        sort_quick(a,0,a.length-1);
    }

    private static void sort_quick(Comparable[]a,int lo,int hi){
        int j;
        if (hi<=lo) return;
        j=partition(a,lo,hi);
        sort_quick(a,lo,j-1);
        sort_quick(a,j+1,hi);
    }
    private static int partition(Comparable[]a,int lo,int hi){
        int i=lo,j=hi+1;
        Comparable v=a[lo];
        while(true){
            while (less(a[++i],v)) if(i==hi)break ;
            while (less(v,a[--j])) if(j==lo)break;
            if(i>=j) break;
            exch(a,i,j);
        }
        exch(a,lo,j);
        return j;
    }




    public static void merge(Comparable[]a,int lo,int mid,int hi){
        //归并排序基本模块，需要另外一个数组
        int i=lo,j=mid+1; //error不能舍去+1
        for(int k=lo;k<=hi;k++){
            aux[k]=a[k];
        }
        for(int k=lo;k<=hi;k++){
            if(i>mid) a[k]=aux[j++];
            else if(j>hi) a[k]=aux[i++];
            else if(less(aux[i],aux[j])) a[k]=aux[i++];
            else a[k]=aux[j++];
        }
    }
    private static void sink(Comparable[] a,int k,int N){
        //下沉
        while(2*k<=N) {
            int j = 2 * k;
            if (j < N && less(a[j], a[j + 1])) j++;
            if (!less(a[k], a[j])) break;
            exch(a, k, j);
            k = j;
        }
    }
    public static void sort_heap(Comparable[] a){
        int N=a.length-1;
        for(int k=N/2;k>=1;k--){
            sink(a,k,N);
        }
        while (N>1){
            exch(a,1,N--);
            sink(a,1,N);
        }
    }


    public static void model1(){
        String[] a=radom(100);
        show(a);
        System.out.println();

        Stopwatch timer=new Stopwatch();
        sort_heap(a);//填写算法
        System.out.println(timer.elapsedTime());

        System.out.println(isSorted(a));
        show(a);
        experiment();
    }


    public static void main(String[] args) {
//        String[] a={"c","g","t","a","g","k"};
//        merge(a,0,3,5);
//        show(a);
        model1();
        }
}
